package zcw.com.lib_leet_code;

import java.util.ArrayDeque;
import java.util.Deque;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/21.<br><br>
 *
 * 每日温度
 */
public class Topic739 {

    public static void main(String[] args) {
        Topic739 instance = new Topic739();

        int[] array = new int[] {73,74,75,71,69,72,76,73};
        Util.printArray(instance.dailyTemperatures(array));

        array = new int[] {30,40,50,60};
        Util.printArray(instance.dailyTemperatures(array));

        array = new int[] {30,60,90};
        Util.printArray(instance.dailyTemperatures(array));
    }

    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for(int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int index = stack.pop();
                result[index] = i - index;
            }

            stack.push(i);
        }

        return result;
    }

    public int[] dailyTemperatures3(int[] temperatures) {
        int[] result = new int[temperatures.length];

        for(int i = temperatures.length - 1; i >= 0; i--) {
            for(int j = i - 1; j >= 0 && temperatures[j] < temperatures[i]; j--) {
                result[j] = i - j;
            }
        }

        return result;
    }

    public int[] dailyTemperatures2(int[] temperatures) {
        int[] result = new int[temperatures.length];

        for(int i = 0; i < temperatures.length; i++) {
            for(int j = i + 1; j < temperatures.length; j++) {
                if(temperatures[i] < temperatures[j]) {
                    result[i] = j - i;
                    break;
                }
            }
        }

        return result;
    }
}
